package com.hh.demo;

import java.awt.Color;
import java.awt.FlowLayout;
import java.util.Arrays;

import javax.swing.*;



public class Stonemerge {
    private static int n;            //石子堆数
    private static int[][] m;        //最优值
    private static int[][] s;
    private static int[] a;          //各堆石子数
    private static int[] backup;     //a的备份
    private static int minScore;     //最小得分
    private static int maxScore;     //最大得分


    public Stonemerge() throws Exception{
        //将石子堆数和随机生成的各堆石子数写入文件
    	/*int no=500;
    	String st=String.valueOf(no);
    	File f = new File("D://eclipse/PHZ/src/Design/dataset/500.txt");
        FileOutputStream fop = new FileOutputStream(f);
        OutputStreamWriter writer = new OutputStreamWriter(fop, "UTF-8");
        writer.append(st);
        writer.append("\r\n");
        while (no-->0){
        	    int num=(int)(Math.random( )*no);
        	    st=String.valueOf(num);
        	    writer.append(st);
                writer.append("\r\n");
        }
        writer.close();


        //读取文件
        BufferedReader bf=new BufferedReader(new FileReader("D://eclipse/PHZ/src/Design/dataset/4.txt"));
        String textLine;
        String str="";
        while((textLine=bf.readLine())!=null){
             str+=textLine+" ";
        }
        String[] numbers=str.split(" ");
        int []number=new int[numbers.length];
        for (int i = 0; i<numbers.length; i++)
    	     number[i]=Integer.parseInt(numbers[i]);
        bf.close();
        */

        //n =number[0];
        System.out.println("问题四：3-3石子合并问题");
        n=Integer.parseInt(JOptionPane.showInputDialog("请输入石子堆数："));
        a = new int[2*n];
        m = new int[2*n][2*n];
        s = new int[2*n][2*n];
        for(int i=1; i<=n; i++)
            //a[i] =number[i];
        {
            a[i]=Integer.parseInt(JOptionPane.showInputDialog("请输入第"+i+"堆石子数："));
        }

        //a会改变，备份一下
        backup = Arrays.copyOf(a, 2*n);

        long startTime1 = System.currentTimeMillis();    //获取开始时间
        minScore = circleMerge(a,0);//type为0，最小得分
        long endTime1 = System.currentTimeMillis();    //获取结束时间

        System.out.println("最小得分程序运行时间：" + (endTime1-startTime1) + "ms");    //输出程序运行时间

        //还原
        m = new int[2*n][2*n];
        //s = new int[2*n][2*n];

        long startTime2 = System.currentTimeMillis();    //获取开始时间
        maxScore = circleMerge(backup, 1);//type为1，最大得分
        long endTime2 = System.currentTimeMillis();    //获取结束时间
        System.out.println("最大得分程序运行时间：" + (endTime2-startTime2) + "ms");    //输出程序运行时间

        System.out.println("最小得分："+minScore);
        System.out.println("最大得分："+maxScore);
        String title="石子合并算法输出";
        JOptionPane.showMessageDialog(null,"最小得分程序运行时间：" + (endTime1-startTime1) + "ms"+
                "\n最大得分程序运行时间：" + (endTime2-startTime2) + "ms"+
                "\n最小得分: "+minScore+"\n最大得分："+maxScore,title,JOptionPane.INFORMATION_MESSAGE);
        JFrame frame=new JFrame();
        JPanel jp=new JPanel();
        JLabel jl = new JLabel();
        jl.setIcon(new ImageIcon("d:\\1.png"));
        jl.setBackground(Color.BLACK);

        jp.add(jl);
        frame.add(jp);

        frame.setTitle("时间复杂度图像");
        frame.setLocation(600, 250);
        frame.setLayout(new FlowLayout());
        frame.setSize(600, 500);
        frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
        frame.setVisible(true);

    }

    //type=0: 最小得分; type=1: 最大得分
    private static int circleMerge(int[] a, int type){
        for(int i=1; i<=n-1; i++) {
            a[n+i] = a[i];
        }

        n = 2*n-1;
        if(type == 0) {
            minSum(a);
        } else {
            maxSum(a);
        }

        n = (n+1)/2;
        int mm = m[1][n];
        for(int i=2; i<=n; i++)//圆排列 转化为 直线排列后，要遍历一下
        {
            if((type==0) && (m[i][n+i-1]<mm) || (type==1) && (m[i][n+i-1]>mm)) {
                mm = m[i][n+i-1];
            }
        }

        return mm;
    }

    public static void minSum(int[] a){
        for(int i=2; i<=n; i++) {
            a[i] = a[i] + a[i-1];
        }

        for(int r=2; r<=n; r++) {
            for(int i=1; i<=n-r+1; i++){
                int j = i+r-1;
                int i1 = i+1;
                int j1 = j;
                if(s[i][j-1] > i) {
                    i1 = s[i][j-1];
                }
                if(s[i+1][j] > i) {
                    j1 = s[i+1][j];
                }
                m[i][j] = m[i][i1-1] + m[i1][j];
                s[i][j] = i1;
                for(int k=j1; k>=i1+1; k--){
                    int q = m[i][k-1] + m[k][j];
                    if(q < m[i][j]){
                        m[i][j] = q;
                        s[i][j] = k;//记录合并的断开位置k
                    }
                }

                m[i][j] = m[i][j] + a[j] -a[i-1];
            }
        }
    }

    public static void maxSum(int[] a){
        for(int i=2; i<=n; i++) {
            a[i] = a[i] + a[i-1];
        }

        for(int r=2; r<=n; r++) {
            for(int i=1; i<=n-r+1; i++){
                int j = i+r-1;
                if(m[i+1][j] > m[i][j-1]) {
                    m[i][j] = m[i+1][j] + a[j] - a[i-1];
                } else {
                    m[i][j] = m[i][j-1] + a[j] - a[i-1];
                }
            }
        }
    }
}
